Modern inventory systems, such as those in storage facilities (e.g., a warehouse) operated by electronic marketplace providers, face significant challenges with respect to managing items in inventory. While storing items within a storage facility and retrieving items for order fulfillment were once traditionally accomplished by human personnel, it is becoming more common for these functions to be performed by a myriad of robotic devices (e.g., mobile drive units (MDUs)). As these devices travel about the storage facility, unexpected obstacles may be encountered such as fallen objects, misplaced storage containers, other MDUs, a human being, liquid on the ground, or the like. Current systems may lack effective contention resolution methods for overcoming these obstacles.
For example, it may be the case that two MDUs need to cross the same space at substantially the same time in the course of performing their respective tasks. This may cause the MDUs to compete for the space. In some systems, each mobile drive unit (MDU) may wait some period of time before requesting access to the space again. This may lead to performance inefficiencies as the MDUs may be stationary while they each wait to ascertain if the space is available. As another example, an MDU may encounter a stationary obstacle (such as a package that has fallen on the warehouse floor) and/or moveable/moving obstacle (such as another MDU, a human, etc.). In this scenario, the area around the obstacle may be labelled as inaccessible and the MDU (and potentially other MDUs) may be redirected to avoid the area. Computing new paths to avoid these areas may lead to delay and even further contentions as the travelable area within the warehouse has decreased. Additionally, current techniques may not allow the system to recover these areas even if the obstacle (e.g., the package, the human, etc.) no longer presents a conflict. Accordingly, current techniques may lead to delays in task completion that may negatively affect the performance of the MDUs operating in the storage facility individually, or as a whole, which may in turn lead to decreased profits for the electronic marketplace provider and a loss of good will with respect to its customers. Embodiments of the invention address these and other problems, individually and collectively.